package 回溯;

import java.util.LinkedList;
import java.util.List;

//216 组合总和3
public class Solution2 {
    public List<List<Integer>> combinationSum3(int k, int n) {
        dfs(1,new LinkedList(),k,n,0);
        return res;
    }
    List<List<Integer>> res = new LinkedList();
    void dfs(int index ,List<Integer> path, int k, int n, int cur){
        if(cur>n || path.size()>k) return;//剪枝
        if(path.size()==k&&cur==n){
            res.add(new LinkedList(path));
            return ;
        }
        for(int i = index ; i <= 9 ; i++){
            path.add(i);
            dfs(i+1,path,k,n,cur+i);
            path.remove(path.size()-1);
        }
    }
}
